package org.moriraaca.google.interview;

public class Histogram {
	int [] H;
	
	public Histogram(int [] H) {
		this.H = H;
	}
	
	private int getMaxIndex() {
		int maxIndex = 0;
		
		for (int i = maxIndex + 1; i < H.length; i++) {
			if (H[maxIndex] < H[i]) maxIndex = i;
		}
		
		return maxIndex;
	}
	
	public int fillHistogram() {
		int maxIndex = getMaxIndex();
		int sum = 0;
		int currentMax = 0;
		
		for (int i = 0; i < maxIndex; i++) {
			sum += Math.max(0, currentMax - H[i]);
			if (H[i] > currentMax) currentMax = H[i];
		}
		
		currentMax = 0;
		for (int i = H.length - 1; i > maxIndex; i--) {
			sum += Math.max(0, currentMax - H[i]);
			if (H[i] > currentMax) currentMax = H[i];
		}
		
		return sum;
	}
}
